#include <vector>
#include <string>

using namespace std;

// 火星词典
// 现有一种使用英语字母的火星语言
// 这门语言的字母顺序对你来说是未知的。
// 给你一个来自这种外星语言字典的字符串列表 words
// words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
// 如果这种说法是错误的，并且给出的 words 不能对应任何字母的顺序，则返回 ""
// 否则，返回一个按新语言规则的 字典递增顺序 排序的独特字符串
// 如果有多个解决方案，则返回其中任意一个
// words中的单词一定都是小写英文字母组成的
// 测试链接 : https://leetcode.cn/problems/alien-dictionary/

// 自己实现的队列
class Solution 
{
public:
    string alienOrder(vector<string>& words) 
    {
        // 入度表，26 种字符
        // indegree[i] 表示字符 'a' + i 没有出现过
        vector<int> indegree(26, -1);
        for(auto& w : words)
        {
            for(char ch : w)
            {
                indegree[ch - 'a'] = 0;
            }
        }

        // 'a' -> 0
		// 'b' -> 1
        //  ......
		// 'z' -> 25
        vector<vector<int>> graph(26);
        // 建图
        for(int i = 0; i < words.size() - 1; ++i)
        {
            string cur = words[i];
            string next = words[i + 1];
            int len = min(cur.size(), next.size());
            int j = 0;
            for(; j < len; ++j)
            {
                if(cur[j] != next[j])
                {
                    // cur[j] 小于 next[j]，则 cur[j] -> next[j]
                    graph[cur[j] - 'a'].emplace_back(next[j] - 'a');
                    ++indegree[next[j] - 'a'];
                    break; // 找到分出大小的字符就可以 break 了
                }
            }
            // 不存在拓扑排序，因为 next 的长度是 len，而 cur 是
            // 比 next 长的，且它们前 len 个字符是相等的，所以 cur
            // 是比 next 大的，应该排在 next 的后面
            if(j < cur.size() && j == next.size()) return "";
        }

        int q[26]{}, l = 0, r = 0;
        int kinds = 0;
        for(int i = 0; i < 26; ++i)
        {
            if(indegree[i] != -1) ++kinds; // 字符的种类加加
            if(indegree[i] == 0) q[r++] = i; // 入队
        }

        // 拓扑排序
        string ans;
        while(l < r)
        {
            int cur = q[l++];
            ans += 'a' + cur;
            for(int next : graph[cur])
            {
                if(--indegree[next] == 0) q[r++] = next;
            }
        }
        // 如果 ans.size() == kinds，则说明存在拓扑排序
        return ans.size() == kinds ? ans : "";
    }
};

// 使用标准库的队列
class Solution 
{
public:
    string alienOrder(vector<string>& words) 
    {
        // 入度表，26 种字符
        // indegree[i] 表示字符 'a' + i 没有出现过
        vector<int> indegree(26, -1);
        for(auto& w : words)
        {
            for(char ch : w)
            {
                indegree[ch - 'a'] = 0;
            }
        }

        // 'a' -> 0
		// 'b' -> 1
        //  ......
		// 'z' -> 25
        vector<vector<int>> graph(26);
        // 建图
        for(int i = 0; i < words.size() - 1; ++i)
        {
            string cur = words[i];
            string next = words[i + 1];
            int len = min(cur.size(), next.size());
            int j = 0;
            for(; j < len; ++j)
            {
                if(cur[j] != next[j])
                {
                    // cur[j] 小于 next[j]，则 cur[j] -> next[j]
                    graph[cur[j] - 'a'].emplace_back(next[j] - 'a');
                    ++indegree[next[j] - 'a'];
                    break; // 找到分出大小的字符就可以 break 了
                }
            }
            // 不存在拓扑排序，因为 next 的长度是 len，而 cur 是
            // 比 next 长的，且它们前 len 个字符是相等的，所以 cur
            // 是比 next 大的，应该排在 next 的后面
            if(j < cur.size() && j == next.size()) return "";
        }

        int kinds = 0;
        queue<int> q;
        for(int i = 0; i < 26; ++i)
        {
            if(indegree[i] != -1) ++kinds; // 字符的种类加加
            if(indegree[i] == 0) q.emplace(i); // 入队
        }

        // 拓扑排序
        string ans;
        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            ans += 'a' + cur;
            for(int next : graph[cur])
            {
                if(--indegree[next] == 0) q.emplace(next);
            }
        }
        // 如果 ans.size() == kinds，则说明存在拓扑排序
        return ans.size() == kinds ? ans : "";
    }
};